DFS on a DAG — Discovery and Finish Times

We first run DFS on the same DAG to record discovery d[v] and finish f[v] times. These times drive the topological order in the next slide.

def dfs(graph):
    color = {u: "WHITE" for u in graph}
    time = 0
    for u in graph:
        if color[u] == "WHITE":
            time = dfs_visit(graph, u, time, color)

def dfs_visit(graph, u, time, color):
    time += 1; d[u] = time; color[u] = "GRAY"
    for v in graph[u]:
        if color[v] == "WHITE":
            time = dfs_visit(graph, v, time, color)
    time += 1; f[u] = time; color[u] = "BLACK"
    return time